UVa/562 - Dividing coins/robado2.cpp

   1 //Robado de: http://www.wretch.cc/blog/celiaailec/19559822
   2 //  Q562: Dividing coins
   3 //  2008.05.28     Celia
   4 //  Method: Dynamic Programming (0-1 knapsack)
   5 //  Result: Accepted
   6 //  Time: 0.130
   7 #include <stdio.h>
   8
   9 #define N 101
  10 #define M 25001
  11
  12 int iabs(int n)
  13 {
  14     return (n > 0)? n : -n;
  15 }
  16 int imax(int n, int m)
  17 {
  18     return (n > m)? n : m;
  19 }
  20
  21 int a[N], v[N][M];
  22
  23 int main()
  24 {
  25     int i, j, t, n, m, sum;
  26     scanf("%d", &t);
  27
  28     while(t-- > 0)
  29     {
  30         scanf("%d", &n);
  31
  32         for(sum = 0, i = 1; i <= n; i++)
  33             scanf("%d", &a[i]), sum += a[i];
  34
  35         m = sum / 2;
  36
  37         for(i = 1; i <= n; i++)
  38         {
  39             for(j = 1; j <= m; j++)
  40             {
  41                 v[i][j] = imax(v[i-1][j], v[i][j-1]);
  42
  43                 if(a[i] <= j)
  44                     v[i][j] = imax(v[i][j], a[i] + v[i-1][j-a[i]]);
  45             }
  46         }
  47
  48         printf("%d\n", iabs(sum - v[n][m] * 2));
  49     }
  50
  51     return 0;
  52 }